package com.zh.note.huawei.onehundred.二叉树遍历;

import java.util.Stack;

/**
 * @Author: zhanghuan
 * @date: 2023/9/16 19:53
 * @description: create it
 */
public class Main {
    public static void main(String[] args) {
        // Scanner sc = new Scanner(System.in);
        // String input = sc.nextLine();
        String input = "a{b{d,e{g,h{,i}}},c{f}}";
        TreeNode root = createTreeNode(input);
        inOrderTraversal(root);

    }

    /**
     * 中序遍历
     *
     * @param root
     */
    private static void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left);
        System.out.print(root.val);
        inOrderTraversal(root.right);
    }

    private static TreeNode createTreeNode(String str) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = null;
        TreeNode currentNode = null;
        boolean isLeftChild = false;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            switch (ch) {
                case '{':
                    stack.push(currentNode);
                    isLeftChild = true;
                    break;
                case ',':
                    isLeftChild = false;
                    break;
                case '}':
                    stack.pop();
                    break;
                default:
                    currentNode = new TreeNode(ch);
                    if (root == null) {
                        root = currentNode;
                    } else {
                        if (isLeftChild) {
                            TreeNode peek = stack.peek();
                            peek.left = currentNode;
                        } else {
                            TreeNode peek = stack.peek();
                            peek.right = currentNode;
                        }
                    }
                    break;
            }
        }
        return root;

    }

    static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
}
